package com.note.feng.leetcode.algorithms.easy.linked;

import java.util.Stack;

public class TwoHundredThirtyFour {

    /**
     * 234 回文链表
     * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     *
     * 示例 1：
     *
     * 输入：head = [1,2,2,1]
     * 输出：true
     * 示例 2：
     *
     * 输入：head = [1,2]
     * 输出：false
     *
     * 提示：
     *
     * 链表中节点数目在范围[1, 105] 内
     * 0 <= Node.val <= 9
     *
     * 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/palindrome-linked-list
     */
    /**
     * 解法：迭代
     * 借助栈，先遍历链表，把值存入栈中，
     * 再次遍历链表的前半段，每个节点的值和栈顶的值对比，
     * 不一致，返回false，否则返回true
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if(head == null){
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        ListNode node = head;
        while (node != null){
            stack.push(node.val);
            node = node.next;
        }
        int size = stack.size() / 2;
        node = head;
        for (int i = 0; i < size; i++) {
            if(stack.pop() != node.val){
                return false;
            }
            node = node.next;
        }
        return true;
    }
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
